Please click on ads to support us..

Python Code:

import io,os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):


    n = int(input())
    arr = list(map(int,input().split()))

    dp = [False]*(n+1)
    dp[-1] = True


    for i in range(n):
        if dp[i-1] and i + arr[i] < n:   dp[i+arr[i]] = True
        if i - arr[i] >= 0 and dp[i-arr[i]-1]:  dp[i] = True


    
    if dp[n-1]:   print("YES")
    else:  print("NO")





















T = int(input())
t = 1
while t<=T:
    main(t)
    t += 1

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5 + 100;
int n, a[N], dp[N];
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = 0;
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(dp[i - 1] && i + a[i] <= n) dp[i + a[i]] = 1;
        if(i - a[i] >= 1 && dp[i - a[i] - 1]) dp[i] = 1;
    }
    cout << (dp[n] ? "YES" : "NO") << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}

// .........................................................................................................................
// .........................................................................................................................
// .........................................................................................................................
// ..............................................................]OOO]]/O]`.................................................
// .........................................................../OO@@@@@@@OOOOO`..............................................
// ........................................................./@@@@@@@@@@@@@@@@@O\............................................
// ........................................................O@@@@@@@@@@@@@@@@@@@OO\..........................................
// ........................................................=@@@@@@@@OOOO@@@@@@@@@^..........................................
// .........................................................O@@@@@@OoooOO@@@@@@@@...........................................
// ..........................................................\@@@OOOOOOOO@@@@@@@`...........................................
// ...........................................................O*,[[[*OOOOOOO@O^.............................................
// ...........................................................,,*,`*,Ooo]oOOO/..............................................
// .......................................................,/@@@ooo^/OOOOOOO.................................................
// ...................................................=@@@@@@@@@oo/\OOOOOO@^................................................
// .............................................,]@@^..@@@@@@@@@@\,\oooO@@@@@@`.............................................
// ...........................................@@@@@@@^.=@@@@@@@@@@@OOO@@@@@@@@@.=\..........................................
// ..........................................=@@@@@@@@.*@@@@@@@@@@@@@@@@@@@@@@@..@@\`.......................................
// ........................................@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@@@@@/.=@@@@@@\`...................................
// ......................................,@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@^.=@@@@@@@@@\.................................
// ....................................,@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@.*@@@@@@@@@@@@................................
// .................................../@@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@@*=@@@@@@@@@@@@@]`.............................
// ................................,@@@@@@@@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@@@@^*@@@@@@@@@@@@@@@@@@\..........................
// ..............................,@@@@@@@@@@@@@@@@@@@@^`@@@@@@@@@@@@@@@@@@@@@o,@@@@@@@@@@@@@@@@@@@@O........................
// ............................,@@@@@@@@@@@@@@@@@@@@@@**@@@@@@@@@@@@@@@@@@@@/*/@@@@@@@@@@@@@@@@@@@@@@@@@@OOo\]]*****........
// ........................../@@@@@@@@@@@@@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@@^\@@@@/..[@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@O\`.....
// ......................./@@@@@@@@@@@@@/`.=@@@@@@@@@^`@@@@@@@@@@@@@@@@@@@@/*@@@@@........[\@@@@@@@@@@@@@@@@@@@@@@@@@@@\*...
// ....................,/@@@@@@@@@@/[....,@@@@@@@@@@@*,@@@@@@@@@@@@@@@@@@@@,@@@@/..............,[O@@@@@OOOoOoooOOOoOOOOO*...
// ..................,@@@@@@@@@@/.......=@@@@@@@@@@@^*=@@@@@@@@@@@@@@@@@@@\@@@@`....................=OOOooOoooooooOOOooo*...
// ................,@@@@@@@@@@`........,@@@@@@@@@@@@`*@@@@@@@@@@@@@@@@@@@/@@@`...................../OOOOOOOoooooOOOOOO^=....
// .............../@@@@@@@@@`..........@@@@@@@@@@@@/*=@@@@@@@@@@@@@@@@@O@@[......................./OOOOOOOOOooOOOOOOOO\o*...
// ............../@@@@@@@@`...........=@@@@@@@@@@@@=\@@@@@@@@@@@@@@@@@@@/........................=OOOOOOOOOOOOOOOOOOOOoo*...
// ............,@@@@@@@/..............[@[@@@@@@@@@@@@@@@@@@@@@@@@@@@@`...........................=OOOOOO@OOO@OOOOOOOOOOO^...
// ...........,@@@@@@@/.................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@].........................OOOO@OOO@OOOOOOO@@OOOO`...
// ..........,@@@@@@@`..................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^........................=O@@@@@@@@@@@@@@@@@@/.....
// ..........*\@@@@/....................=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^.........................,O@@@@@@@@@@@@@@@O^......
// .........*=oooO[.....................=@@@OOO@@@@@@@@@@@@@@@@@@@@@@@@@@............................,OO@@@@@@@@@@O/........
// .........oO^.=^......................=@@@OO@@@@@@@@@@@@@@@@@@@@@@@@@@OO.............................*[\OOOOO/[*..........
// ........,O^..=^.......................OOOOOOOO@@@@@@@@@@@@@@@@@@@@@@OOOO`................................................
// .........O\...........................OOOOOOOOO@@@@@@@@@@@@@@@@@OOOOOOOOO`...............................................
// ..........,..........................=OOOOOOOOOOO@@@@@@@@@@@OOOOOOOOOOOOOO\..............................................
// .....................................OOOOOOOOOOOOOO@@@@@@@@@@@@@@OOOOOOOOOOO.............................................
// .....................................OOOOOOOOOOOOOOO@^.,\@@@@@@@@@@@@@@@OOOOO`...........................................
// .....................................,[email protected]@@@@@@@@@@O@@@OOOOO^..........................................
// .......................................OOOOOOOOOOOOO^......,@@@@@@@@@@@@@OOOOOO^.........................................
// .......................................=OOOOOOOOOOOO^........,@@@@@@@OOOOOOOOOOO^........................................
// ........................................OOOOOOOOOOOOO..........\@@@@@@@@OOOOOOOOO`.......................................
// ........................................=OOOOOOOOOOOO............\@@@@@@@OOOOOOOOO.......................................
// ........................................=OOOOOOOOOOOO^.............\@@@@@@@OOOOOOO\......................................
// .........................................OOOOOOOOOOOO\..............=@@@@@@@@OOOOOO\.....................................
// **....********...........................OOOOOOOOOOO@@`..............,@@@@@@@@@OOOOO^....................................
// **************..........................OOOOOOOOO@@@@`.................=@@@@@@@@@@OOO`...................................
// ********************....***.............OOOOOOO@@@@@^..................,@@@@@@@@@@@@O....................................
// ********************..*************.....=OOOO@@@@@@^....................=@@@@@@@@@@@/....................................
// .************************************...=OOOO@@@@@@^....................O@@@@@@@@@@@.....................................
// ...************************************.=OOOO@@@@@@^.................../@@@@@@@@@@@^.....................................
// ......*..****************************.*.=OOO@@@@@@@^..................,@@@@@@@@@@@O......................................
// **...*******]]]]]]]]]]]]]]]]]]]]]]]`****=OOO@@@@@@@`..................=@@@@@@@@@@@^......................................
// ********=oooooooo**ooo*******************OOO@@@@@@O*******************O@@@@@@@@@@O***************************************
// *****************************************OO@@@@@@@^*******************O@@@@@@@@@@^***************************************
// *****************************************OO@@@@@@@********************O@@@@@@@@@/****************************************
// *****************************************=O@@@@@@O********************O@@@@@@@@O*****************************************
// *****************************************,O@@@@@@\.******************/@@@@@@@@O******************************************
// ********************************..........=OOOO@@O.*****.....******.=@@@@@@@@O*******************************************
// *********************************.......*.,@@@@@@^....**........***./@@OOO@@/********************************************
// **********************************........=@@@@@@^....****.......*.,@@@@@@@O************************..*******************
// *******************************...........@@@@@@@O..............*./@@@@@@@@^.******.*************************************
// **.......................................=@@@@@@@@*..............=@@@@@@@@@@^******.*************************************
// ........................................./@@@@@@@@...............@@@@@@@@@@@@^...........................................
// *.......................................=@@@@@@@@^..............@@@@@@@@@@@@@@\*...*************.........................
// ........................................@@@@@@@@^..............,@@@@@@@@@@@@@@@@@O]`*********..*.........................
// .......................................@@@@@@@@@^............****]/O@@@@@@@@@@@@@@@@O**************......................
// ......................................=@@@@@@@@@^.....**********,oooOOOOOO@@@@@@@@@@@^***************....................
// .................................**...=@@@@@@@@@^***************,oooooOOOOOoooooooo/`******************..................



Comments

Submit
0 Comments
More Questions

1302. Deepest Leaves Sum
1209. Remove All Adjacent Duplicates in String II
994. Rotting Oranges
983. Minimum Cost For Tickets
973. K Closest Points to Origin
969. Pancake Sorting
967. Numbers With Same Consecutive Differences
957. Prison Cells After N Days
946. Validate Stack Sequences
921. Minimum Add to Make Parentheses Valid
881. Boats to Save People
497. Random Point in Non-overlapping Rectangles
528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST